We have two tools for two different jobs. Choosing the right one is critical.
- Dijkstra's Algorithm finds shortest paths in any graph, but strictly requires non-negative edge weights.
- It uses a greedy approach, prioritizing the node with the smallest known distance via a Priority Queue.
- The typical complexity is $O((V+E) \log V)$ when implemented with a binary heap.
- Topological Sort is used to find shortest paths in Directed Acyclic Graphs (DAGs) only.
- This method works correctly even if the graph contains negative edge weights.
- It processes nodes in linear order, resulting in a highly efficient $O(V + E)$ time complexity.
Algorithm Comparison Summary
| Feature | Dijkstra's Algorithm | DAG Shortest Path (w/ Topo Sort) |
|---|---|---|
| Graph Type | Any graph (cyclic OK) | DAGs only |
| Negative Weights? | No (Fails) | Yes (Works) |
| Core Data Structure | Priority Queue (Min-Heap) | Simple Queue (FIFO) |
| Time Complexity | $O((V+E) \log V)$ | $O(V + E)$ |